1. Field of the Invention
The present invention relates to an array multiplier, and particularly, to a structure and method of array multiplication.
2. Description of the Prior Art
Multiplication is one of basic arithematics commonly used in computer systems. Because of its complex computation involved, a great deal of time is thus required to calculate the final product of one number multiplied by another. The above is true especially for performing multiplication of two numbers having large amount of bits, which is commonly done in a software manner.
An array multiplier has been disclosed based on the observation that partial products calculated during the multiplication process can be independently computed in parallel. For example, let X=X.sub.3 X.sub.2 X.sub.1 X.sub.0 and Y=Y.sub.3 Y.sub.2 Y.sub.1 Y.sub.0 be 4-bit binary integers representing multiplicand and multiplier, respectively, and P=P.sub.7 P.sub.6 . . . P.sub.1 P.sub.0 be 8-bit product, which are shown below along with their partial products.
______________________________________ X.sub.3 X.sub.2 X.sub.1 X.sub.0 Multiplicand Y.sub.3 Y.sub.2 Y.sub.1 Y.sub.0 Multiplier X.sub.3 Y.sub.0 X.sub.2 Y.sub.0 X.sub.1 Y.sub.0 X.sub.0 Y.sub.0 Partial Product X.sub.3 Y.sub.1 X.sub.2 Y.sub.1 X.sub.1 Y.sub.1 X.sub.0 Y.sub.1 Partial product X.sub.3 Y.sub.2 X.sub.2 Y.sub.2 X.sub.1 Y.sub.2 X.sub.0 Y.sub.2 Partial Product +) X.sub.3 Y.sub.3 X.sub.2 Y.sub.3 X.sub.1 Y.sub.3 X.sub.0 Y.sub.3 Partial Product P.sub.7 P.sub.6 P.sub.5 P.sub.4 P.sub.3 P.sub.2 P.sub.1 P.sub.0 Product ______________________________________
Each bit of the multiplier Y is timed to the multiplicand X to produce a corresponding partial product, followed by adding all these partial products in the manner shown above to obtain the final product P. The arrangement mentioned above is well suited to hardware implementation. FIG. 1 shows a structure 10 illustrating the arrangement of the partial products constructed by a 4.times.4 array of standard AND gates 12.
In order to complete the process of the multiplication, an array of adders is further required to add the partial products together. FIG. 2A shows a structure illustrating a 4.times.4 array multiplier 20 consisted of a 4.times.4 partial product array 201 and an array of adders 203. Inside the array of adders 203, HA 2030 denotes a standard half adder that has two input operands and two outputs (i.e., sum and carry), and FA 2032 denotes a standard full adder that has three input operands and two outputs. Furthermore, WTA 2034 or 2036 denotes a Wallace Tree adder that can perform addition with multiple (generally more than three) input operands. For example, the WTA 2034 that generates P.sub.3 has five input operands, and the WTA 2036 that generates P.sub.4 or P.sub.2 has four input operands. As the WTA 2034 or 2036 is not a standard component, it is generally constructed by two layers of standard logic components. FIG. 2B shows one implementation of the WTA 2034. A full adder FA which takes three inputs and a half adder HA1 which takes two inputs are used as the first layer. Therefore, the outputs from the full adder FA and the half adder HA1, respectively, are fed to another half adder HA2, which generates a sum bit and a carry bit. For the WTA 2036 which generates P.sub.2 or P.sub.4, for example, two layers of half adders HA1, HA2, and HA3 are arranged as shown in FIG. 2C. One of the main drawbacks of the array multiplier with Wallace Tree adder is its irregularity in the layout, which wastes a substantial portion of area, and increases difficulties in laying out the circuit.
In order to eliminate the drawback mentioned above, another multiplier 30 has been disclosed as shown FIG. 3, wherein carry-saved adders are used. Beginning from the second row of the partial products 302, half adders HAs or full adders FAs are used to calculate the sums of the partial products of the current row and its precedent row. For each array cell, one of the operands inputting to the half adder HA or the full adder FA is the resultant output of a corresponding AND gate in the same cell. Another one or ones of the operands inputting to the half adder HA or the full adder FA are connected as the arrows point. It is noted that carriers do not propagate in the same row but to the next row. Consequently, an additional row of adders 304 is required to add the sums and carriers from the last row of the partial products 302. In the 4.times.4 carry-saved array multiplier 30 in FIG. 3, eight full adders FAs, four half adders HAs, and sixteen standard AND gates are required.
Although each adder in the additional row 304 has more uniform input bits than that in the Wallace Tree adders 203 (FIG. 2A), the array cells become irregular in their layout due to the introduction of the half adders HAs and the full adders FAs. Moreover, except for the first row of the partial products 302 which does not include adders, other rows of the partial products 302 still suffer from irregularity in layout since some cells contain adders and some do not.